﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static LightCAD.MathLib.CSG.Mesh;
using static System.Windows.Forms.VisualStyles.VisualStyleElement.Rebar;

namespace LightCAD.MathLib.CSG
{
    partial class Mesh
    {
        public class TriTripleTemp
        {
            public TopoTri t0, t1, t2;
            public TriTripleTemp(TopoTri tp0, TopoTri tp1, TopoTri tp2)
            {
                this.t0 = tp0;
                this.t1 = tp1;
                this.t2 = tp2;
            }
        };
        public class GenericVertType
        {
            public TopoVert concrete;
            public Vec3 coord;

            public bool boundary;
            public int idx; // temporary for triangulation marshalling

            public List<GenericEdgeType> edges = new List<GenericEdgeType>();
        };
        public class IsctVertType : GenericVertType
        {
            public GluePointMarker glue_marker;
        }
        public class OrigVertType : GenericVertType { };

       public class GenericEdgeType
        {
            public TopoEdge concrete;

            public bool boundary;
            public int idx; // temporary for triangulation marshalling

            public GenericVertType[] ends = new GenericVertType[2];
            public List<IsctVertType> interior = new List<IsctVertType>();
        };
        public class IsctEdgeType : GenericEdgeType
        {
            // use to detect duplicate instances within a triangle
            public TopoTri other_tri_key;
        };
        public class OrigEdgeType : GenericEdgeType
        { };
        public class SplitEdgeType : GenericEdgeType
        { };

        public class GenericTriType
        {
            public TopoTri concrete;

            public GenericVertType[] verts = new GenericVertType[3];
        };
        public  class GluePointMarker
        {
            // list of all the vertices to be glued...
            public List<IsctVertType> copies = new List<IsctVertType>();
            public bool split_type; // splits are introduced
                                    // manually, not via intersection
                                    // and therefore use only e pointer
            public bool edge_tri_type; // true if edge-tri intersection
                                       // false if tri-tri-tri
            public TopoEdge e;
            public TopoTri[] t = new TopoTri[3];
        };



       public class IsctProblem : TopoCache
        {

            IterPool<GluePointMarker> glue_pts = new IterPool<GluePointMarker>();
            IterPool<TriangleProblem> tprobs = new IterPool<TriangleProblem>();

            IterPool<IsctVertType> ivpool = new IterPool<IsctVertType>();
            IterPool<OrigVertType> ovpool = new IterPool<OrigVertType>();
            IterPool<IsctEdgeType> iepool = new IterPool<IsctEdgeType>();
            IterPool<OrigEdgeType> oepool = new IterPool<OrigEdgeType>();
            IterPool<SplitEdgeType> sepool = new IterPool<SplitEdgeType>();
            IterPool<GenericTriType> gtpool = new IterPool<GenericTriType>();

            Empty3d empty3d;
            List<Vec3> quantized_coords = new List<Vec3>();
            Quantization quantizer = new Quantization();

            public IsctProblem(Mesh mesh)
                : base(mesh)
            {
                empty3d = new Empty3d(quantizer);
                // initialize all the triangles to NOT have an associated tprob
                for (var t = base.tris.getFirst(); t != null; t = base.tris.getNext(t))
                {
                    t.datum.data = null;
                }

                // Calibrate the quantization unit...
                double maxMag = 0.0;
                for (int ind = 0; ind != base.mesh.verts.size(); ++ind)
                {
                    maxMag = Math.Max(maxMag, Vec3.abs(base.mesh.verts[ind].pos.clone()).Max());
                }
                quantizer.callibrate(maxMag);

                // and use vertex auxiliary data to store quantized vertex coordinates
                quantizeVerts(quantizer);
            }

            internal void commit()
            {

                // record which vertices are live
                var live_verts = new List<bool>().makeSize(mesh.verts.size(), false);
                for (var vert = verts.getFirst(); vert != null; vert = verts.getNext(vert))
                { // cache.verts
                    live_verts[vert.datum.@ref] = true;
                }

                // record which triangles are live, and record connectivity
                var live_tris = new List<bool>().makeSize(mesh.tris.size(), false);
                for (var tri = tris.getFirst(); tri != null; tri = tris.getNext(tri))
                {// cache.tris
                    live_tris[tri.datum.@ref] = true;
                    for (int k = 0; k < 3; k++)
                        mesh.tris[tri.datum.@ref][k] = tri.datum.verts[k].@ref;
                }

                // compact the vertices and build a remapping function
                var vmap = new List<int>().makeSize(mesh.verts.size());
                int write = 0;
                for (int read = 0; read < mesh.verts.size(); read++)
                {
                    if (live_verts[read])
                    {
                        vmap[read] = write;
                        mesh.verts[write] = mesh.verts[read];
                        write++;
                    }
                    else
                    {
                        vmap[read] = INVALID_ID;
                    }
                }
                mesh.verts.resize(write);

                // rewrite the vertex reference ids
                for (var vert = verts.getFirst(); vert != null; vert = verts.getNext(vert))
                { // cache.verts
                    vert.datum.@ref = vmap[vert.datum.@ref];
                }

                var tmap = new List<int>().makeSize(mesh.tris.size());
                write = 0;
                for (int read = 0; read < mesh.tris.size(); read++)
                {
                    if (live_tris[read])
                    {
                        tmap[read] = write;
                        mesh.tris[write] = mesh.tris[read];
                        for (int k = 0; k < 3; k++)
                            mesh.tris[write][k] = vmap[mesh.tris[write][k]];
                        write++;
                    }
                    else
                    {
                        tmap[read] = INVALID_ID;
                    }
                }
                mesh.tris.resize(write);

                // rewrite the triangle reference ids
                for (var tri = tris.getFirst(); tri != null; tri = tris.getNext(tri))
                { // cache.tris
                    tri.datum.@ref = tmap[tri.datum.@ref];
                }
            }

            internal void findIntersections()
            {

                int nTrys = 5;
                //perturbPositions(); // always perturb for safety...
                while (nTrys > 0)
                {
                    if (!tryToFindIntersections())
                    {
                        reset();
                        perturbPositions();
                        nTrys--;
                    }
                    else
                    {
                        break;
                    }
                }
                if (nTrys <= 0)
                {
                    Cork.CORK_ERROR("Ran out of tries to perturb the mesh");
                    //std::logic_error
                    return;
                    //exit(1);
                }

                // ok all points put together,
                // all triangle problems assembled.
                // Some intersection edges may have original vertices as endpoints
                // we consolidate the problems to check for cases like these.
                int counter = 0;
                for (var tprob = tprobs.getFirst(); tprob != null; tprob = tprobs.getNext(tprob))
                {
                    tprob.datum.consolidate(this);
                    ++counter;
                }
            }

            private void reset()
            {
                throw new NotImplementedException();
            }
            TriangleProblem getTprob(TopoTri t)
            {
                if (t.@ref == 4875 || t.@ref == 4199)
                {
                    int stop = 1;
                }
                var prob = (TriangleProblem)t.data;
                if (prob == null)
                {
                    t.data = prob = tprobs.alloc().datum;
                    prob.init(this, t);
                }
                return prob;
            }
            GluePointMarker newGluePt()
            {
                var glue = glue_pts.alloc();
                glue.datum.split_type = false;
                return glue.datum;
            }
            private bool tryToFindIntersections()
            {
                empty3d.resetCounts();
                // Find all edge-triangle intersection points
                //for_edge_tri([&](Eptr eisct, Tptr tisct).bool{
                bvh_edge_tri((eisct, tisct) =>
                {
                    if (checkIsct(eisct, tisct))
                    {
                        var glue = newGluePt();
                        glue.edge_tri_type = true;
                        glue.e = eisct;
                        glue.t[0] = tisct;
                        // first add point and edges to the pierced triangle
                        //      if (tisct.ref == 46445 || tisct.ref == 46510 )
                        //{
                        //	int toto = 0;
                        //}
                        if (tisct.@ref == 7540)
                        {
                        }
                        IsctVertType iv = getTprob(tisct).addInteriorEndpoint(this, eisct, glue);
                        for (int ind = 0; ind != eisct.tris.size(); ++ind)
                        {
                            getTprob(eisct.tris[ind]).addBoundaryEndpoint(this, tisct, eisct, iv);
                        }
                    }
                    if (empty3d.hasDegeneracies())
                        return false; // break
                    else
                        return true; // continue
                });
                if (empty3d.hasDegeneracies())
                {
                    return false;   // restart / abort
                }

                // we're going to peek into the triangle problems in order to
                // identify potential candidates for Tri-Tri-Tri intersections
                var triples = new List<TriTripleTemp>();
                for (var tprob = tprobs.getFirst(); tprob != null; tprob = tprobs.getNext(tprob))
                {
                    var t0 = tprob.datum.the_tri;
                    // Scan pairs of existing edges to create candidate triples
                    for (int i = 0; i < tprob.datum.iedges.size(); i++)
                    {
                        var t1 = tprob.datum.iedges[i].other_tri_key;
                        if (t0.i < t1.i)//C++中比较指针无法处理，采用index替代
                        {
                            for (int j = i + 1; j < tprob.datum.iedges.size(); j++)
                            {
                                var t2 = tprob.datum.iedges[j].other_tri_key;
                                // This triple might be considered three times,
                                // one for each triangle it contains.
                                // To prevent duplication, only proceed if this is
                                // the least triangle according to an arbitrary ordering
                                if (t0.i < t2.i)
                                {
                                    // now look for the third edge.  We're not
                                    // sure if it exists...
                                    var prob1 = (TriangleProblem)(t1.data);
                                    for (int ind = 0; ind != prob1.iedges.size(); ++ind)
                                    {
                                        if (prob1.iedges[ind].other_tri_key == t2)
                                        {
                                            // ADD THE TRIPLE
                                            triples.push_back(new TriTripleTemp(t0, t1, t2));
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
                // Now, we've collected a list of Tri-Tri-Tri intersection candidates.
                // Check to see if the intersections actually exist.
                for (int ind = 0; ind != triples.size(); ++ind)
                {
                    TriTripleTemp t = triples[ind];
                    if (!checkIsct(t.t0, t.t1, t.t2)) continue;

                    // Abort if we encounter a degeneracy
                    if (empty3d.hasDegeneracies()) break;

                    var glue = newGluePt();
                    glue.edge_tri_type = false;
                    glue.t[0] = t.t0;
                    glue.t[1] = t.t1;
                    glue.t[2] = t.t2;
                    getTprob(t.t0).addInteriorPoint(this, t.t1, t.t2, glue);
                    getTprob(t.t1).addInteriorPoint(this, t.t0, t.t2, glue);
                    getTprob(t.t2).addInteriorPoint(this, t.t0, t.t1, glue);
                }
                if (empty3d.hasDegeneracies())
                {
                    return false;   // restart / abort
                }

                return true;

            }


            GeomBlob<TopoEdge> edge_blob(TopoEdge e)
            {
                var blob = new GeomBlob<TopoEdge>();
                blob.bbox = buildBox(e);
                blob.point = (blob.bbox.minp + blob.bbox.maxp) / 2.0;
                blob.id = e;
                return blob;
            }

            void bvh_edge_tri(Func<TopoEdge, TopoTri, bool> func)
            {
                var edge_geoms = new List<GeomBlob<TopoEdge>>();
                base.edges.for_each((e) =>
                {
                    edge_geoms.push_back(edge_blob(e));
                });
                var edgeBVH = new AABVH<TopoEdge>(edge_geoms);

                // use the acceleration structure
                bool aborted = false;
                base.tris.for_each((t) =>
                {
                    // Debug.Print("tri:"+ t.@ref);

                    // compute BBox
                    BBox3 bbox = buildBox(t);
                    if (!aborted)
                    {
                        edgeBVH.for_each_in_box(bbox, t.@ref, (e) =>
                        {
                            if (!func(e, t))
                                aborted = true;
                        });
                    }
                });
            }


            bool checkIsct(TopoEdge e, TopoTri t)
            {
                // simple bounding box cull; for acceleration, not correctness
                BBox3 ebox = buildBox(e);
                BBox3 tbox = buildBox(t);
                if (!BBox3.hasIsct(ebox, tbox))
                    return false;

                // must check whether the edge and triangle share a vertex
                // if so, then trivially we know they intersect in exactly that vertex
                // so we discard this case from consideration.
                if (hasCommonVert(e, t))
                    return false;

                Empty3d.TriEdgeIn input = new Empty3d.TriEdgeIn();
                marshallArithmeticInput(input, e, t);

                //#define USE_ORIGINAL_CODE
                //# ifdef USE_ORIGINAL_CODE
                //                //bool empty = empty3d.isEmpty(input);
                //                bool empty = empty3d.emptyExact(input);
                //#else
                bool empty = empty3d.emptyApprox(input);
                //#endif
                return !empty;
            }

            bool checkIsct(TopoTri t0, TopoTri t1, TopoTri t2)
            {
                // This function should only be called if we've already
                // identified that the intersection edges
                //      (t0,t1), (t0,t2), (t1,t2)
                // exist.
                // From this, we can conclude that each pair of triangles
                // shares no more than a single vertex in common.
                //  If each of these shared vertices is different from each other,
                // then we could legitimately have a triple intersection point,
                // but if all three pairs share the same vertex in common, then
                // the intersection of the three triangles must be that vertex.
                // So, we must check for such a single vertex in common amongst
                // the three triangles
                TopoVert common = commonVert(t0, t1);
                if (common != null)
                {
                    for (int i = 0; i < 3; i++)
                        if (common == t2.verts[i])
                            return false;
                }

                Empty3d.TriTriTriIn input = new Empty3d.TriTriTriIn();
                marshallArithmeticInput(input, t0, t1, t2);
                //bool empty = empty3d.isEmpty(input);
                bool empty = empty3d.emptyExact(input);
                return !empty;
            }


            private void perturbPositions()
            {
                //加入微小扰动，是如何保证安全的？

                const double EPSILON = 1.0e-5; // perturbation epsilon
                for (int ind = 0; ind != quantized_coords.size(); ++ind)
                {
                    var perturbation = new Vec3(quantizer.quantize(Utils.drand(-EPSILON, EPSILON)),
                           quantizer.quantize(Utils.drand(-EPSILON, EPSILON)),
                           quantizer.quantize(Utils.drand(-EPSILON, EPSILON)));
                    quantized_coords[ind] += perturbation;
                }
            }

            internal void print()
            {

            }
            private void writeTprob(TriangleProblem tpr)
            {
                const string path = @"c:\temp\corknet.txt";
                var sb = new StringBuilder();
                sb.AppendLine("the_tri:" + tpr.the_tri.@ref.ToString());
                sb.AppendLine("iverts:" + tpr.iverts.Count);
                foreach (var iv in tpr.iverts)
                {
                    sb.AppendLine("iv:" + iv.idx);
                }
                
                sb.AppendLine("iedges:" + tpr.iedges.Count);
                foreach (var ie in tpr.iedges)
                {
                    if (ie == null)
                        sb.AppendLine("ie:NULL");
                    else
                        sb.AppendLine("ie:" + ie.idx);
                }

                sb.AppendLine("overts:" + tpr.overts.Length);
                foreach (var ov in tpr.overts)
                {
                    sb.AppendLine("ov:" + ov.idx);
                }

                sb.AppendLine("oedges:" + tpr.oedges.Length);
                foreach (var oe in tpr.oedges)
                {
                    if (oe == null)
                        sb.AppendLine("oe:NULL");
                    else
                        sb.AppendLine("oe:" + oe.idx);
                }

                sb.AppendLine("gtris:" + tpr.gtris.Count);
                foreach (var gt in tpr.gtris)
                {
                    //if (gt.concrete == null)
                    //    sb.AppendLine("gt concrete:NULL");
                    //else
                    //    sb.AppendLine("gt:" + gt.concrete.@ref);
                    foreach(var gv in gt.verts)
                    {
                        sb.AppendLine("gv:" + gv.coord.ToString());
                    }
                }
                File.AppendAllText(path, sb.ToString());
            }
            internal void resolveAllIntersections()
            {
                // solve a subdivision problem in each triangle
                for (var tprob = tprobs.getFirst(); tprob != null; tprob = tprobs.getNext(tprob))
                {
                    //var refid = tprob.datum.the_tri.@ref;
                    //if (Array.IndexOf(indexArr, refid) < 0)
                    //{
                    //    Debug.Print(tprob.datum.the_tri.@ref.ToString());
                    //}
                    tprob.datum.subdivide(this);
                    writeTprob(tprob.datum);
                }

                // now we have diced up triangles inside each triangle problem

                // Let's go through the glue points and create a new concrete
                // vertex object for each of these.
                for (var glue = glue_pts.getFirst(); glue != null; glue = glue_pts.getNext(glue))
                {
                    createRealPtFromGluePt(glue.datum);
                }

                var ecache = new EdgeCache(this);

                // Now that we have concrete vertices plugged in, we can
                // go through the diced triangle pieces and create concrete triangles
                // for each of those.
                // Along the way, let's go ahead and hook up edges as appropriate
                for (var tprob = tprobs.getFirst(); tprob != null; tprob = tprobs.getNext(tprob))
                {
                    createRealTriangles(tprob.datum, ecache);
                }

                // mark all edges as normal by zero-ing out the data pointer
                for (var e = base.edges.getFirst(); e != null; e = base.edges.getNext(e))
                {
                    e.datum.data = 0;
                }
                // then iterate over the edges formed by intersections
                // (i.e. those edges without the boundary flag set in each triangle)
                // and mark those by setting the data pointer
                for (var ie = iepool.getFirst(); ie != null; ie = iepool.getNext(ie))
                {
                    // every ie must be non-boundary
                    TopoEdge e = ecache.maybeEdge(ie.datum);
                    Utils.ENSURE(e != null);
                    e.data = 1;
                }
                for (var se = sepool.getFirst(); se != null; se = sepool.getNext(se))
                {
                    //if(se.boundary)    return; // continue
                    TopoEdge e = ecache.maybeEdge(se.datum);
                    Utils.ENSURE(e != null);
                    e.data = 1;
                }

                // This basically takes care of everything EXCEPT one detail
                // *) The base mesh data structures still need to be compacted

                // This detail should be handled by the calling code...
            }
            void createRealPtFromGluePt(GluePointMarker glue)
            {
                Utils.ENSURE(glue.copies.size() > 0);
                var v = base.newVert();
                var data = base.mesh.verts[v.datum.@ref];
                data.pos = glue.copies[0].coord;
                fillOutVertData(glue, data);
                for (int ind = 0; ind != glue.copies.size(); ++ind)
                    glue.copies[ind].concrete = v.datum;
            }

            void createRealTriangles(TriangleProblem tprob, EdgeCache ecache)
            {
                for (int ind = 0; ind != tprob.gtris.size(); ++ind)
                {
                    var gt = tprob.gtris[ind];

                    var t = base.newTri();
                    gt.concrete = t.datum;
                    var tri = base.mesh.tris[t.datum.@ref];
                    for (int k = 0; k < 3; k++)
                    {
                        var v = gt.verts[k].concrete;
                        t.datum.verts[k] = v;
                        v.tris.push_back(t.datum);
                        tri[k] = v.@ref;

                        var e = ecache.getTriangleEdge(gt, k, tprob.the_tri);
                        e.tris.push_back(t.datum);
                        t.datum.edges[k] = e;
                    }
                    fillOutTriData(t.datum, tprob.the_tri);
                }
                // Once all the pieces are hooked up, let's kill the old triangle!
                base.deleteTri(tprob.the_tri);
            }

            void fillOutTriData(TopoTri piece, TopoTri parent)
            {
                base.mesh.subdivide_tri(piece.@ref, parent.@ref);
            }

            void fillOutVertData(GluePointMarker glue, CorkVertex data)
            {
                if (glue.split_type)
                { // manually inserted split point
                    int v0i = glue.e.verts[0].@ref;
                    int v1i = glue.e.verts[1].@ref;
                    data.isctInterpolate(base.mesh.verts[v0i],
                                         base.mesh.verts[v1i]);
                }
                else
                if (glue.edge_tri_type)
                { // edge-tri type
                    IsctVertEdgeTriInput input = new IsctVertEdgeTriInput();
                    for (int k = 0; k < 2; k++)
                    {
                        int vid = glue.e.verts[k].@ref;
                        input.e[k] = (base.mesh.verts[vid]);
                    }
                    for (int k = 0; k < 3; k++)
                    {
                        int vid = glue.t[0].verts[k].@ref;
                        input.t[k] = (base.mesh.verts[vid]);
                    }
                    data.isct(input);
                }
                else
                { // tri-tri-tri type
                    IsctVertTriTriTriInput input = new IsctVertTriTriTriInput();
                    for (int i = 0; i < 3; i++)
                    {
                        for (int j = 0; j < 3; j++)
                        {
                            int vid = glue.t[i].verts[j].@ref;
                            input.t[i, j] = base.mesh.verts[vid];
                        }
                    }
                    data.isct(input);
                }
            }

            public IsctEdgeType find_edge(List<IsctEdgeType> vec, TopoTri key)
            {
                for (int ind = 0; ind != vec.size(); ++ind)
                {
                    var ie = vec[ind];
                    if (ie.other_tri_key == key)
                        return ie;
                }
                return null;
            }

            public TopoVert commonVert(TopoTri t0, TopoTri t1)
            {
                for (int i = 0; i < 3; i++)
                {
                    for (int j = 0; j < 3; j++)
                    {
                        if (t0.verts[i] == t1.verts[j])
                            return t0.verts[i];
                    }
                }
                return null;
            }

            public bool hasCommonVert(TopoTri t0, TopoTri t1)
            {
                return (t0.verts[0] == t1.verts[0] ||
                        t0.verts[0] == t1.verts[1] ||
                        t0.verts[0] == t1.verts[2] ||
                        t0.verts[1] == t1.verts[0] ||
                        t0.verts[1] == t1.verts[1] ||
                        t0.verts[1] == t1.verts[2] ||
                        t0.verts[2] == t1.verts[0] ||
                        t0.verts[2] == t1.verts[1] ||
                        t0.verts[2] == t1.verts[2]);
            }

            public bool hasCommonVert(TopoEdge e, TopoTri t)
            {
                return (e.verts[0] == t.verts[0] ||
                        e.verts[0] == t.verts[1] ||
                        e.verts[0] == t.verts[2] ||
                        e.verts[1] == t.verts[0] ||
                        e.verts[1] == t.verts[1] ||
                        e.verts[1] == t.verts[2]);
            }

            public void disconnectGE(GenericEdgeType ge)
            {
                ge.ends[0].edges.erase(ge);
                ge.ends[1].edges.erase(ge);
                for (int ind = 0; ind != ge.interior.size(); ++ind)
                    ge.interior[ind].edges.erase(ge);
            }


            public IsctVertType newIsctVert(TopoEdge e, TopoTri t, GluePointMarker glue)
            {
                var iv = ivpool.alloc().datum;
                iv.concrete = null;
                iv.coord = computeCoords(e, t);
                iv.glue_marker = glue;
                glue.copies.push_back(iv);
                return iv;
            }
            public IsctVertType newIsctVert(TopoTri t0, TopoTri t1, TopoTri t2, GluePointMarker glue)
            {
                var iv = ivpool.alloc().datum;
                iv.concrete = null;
                iv.coord = computeCoords(t0, t1, t2);
                iv.glue_marker = glue;
                glue.copies.push_back(iv);
                return iv;
            }
            public IsctVertType newSplitIsctVert(Vec3 coords, GluePointMarker glue)
            {
                var iv = ivpool.alloc().datum;
                iv.concrete = null;
                iv.coord = coords;
                iv.glue_marker = glue;
                glue.copies.push_back(iv);
                return iv;
            }
            public IsctVertType copyIsctVert(IsctVertType orig)
            {
                var iv = ivpool.alloc().datum;
                iv.concrete = null;
                iv.coord = orig.coord;
                iv.glue_marker = orig.glue_marker;
                orig.glue_marker.copies.push_back(iv);
                return iv;
            }
            public IsctEdgeType newIsctEdge(IsctVertType endpoint, TopoTri tri_key)
            {
                var ie = iepool.alloc().datum;
                ie.concrete = null;
                ie.boundary = false;
                ie.ends[0] = endpoint;
                endpoint.edges.push_back(ie);
                ie.ends[1] = null; // other end null
                ie.other_tri_key = tri_key;
                return ie;
            }

            public OrigVertType newOrigVert(TopoVert v)
            {
                var ov = ovpool.alloc().datum;
                ov.concrete = v;
                ov.coord = vPos(v);
                ov.boundary = true;
                return ov;
            }
            public OrigEdgeType newOrigEdge(TopoEdge e, OrigVertType v0, OrigVertType v1)
            {
                var oe = oepool.alloc().datum;
                oe.concrete = e;
                oe.boundary = true;
                oe.ends[0] = v0;
                oe.ends[1] = v1;
                v0.edges.push_back(oe);
                v1.edges.push_back(oe);
                return oe;
            }
            public SplitEdgeType newSplitEdge(GenericVertType v0, GenericVertType v1, bool boundary)
            {
                var se = sepool.alloc().datum;
                se.concrete = null;
                se.boundary = boundary;
                se.ends[0] = v0;
                se.ends[1] = v1;
                v0.edges.push_back(se);
                v1.edges.push_back(se);
                return se;
            }

            public GenericTriType newGenericTri(GenericVertType v0, GenericVertType v1, GenericVertType v2)
            {
                var gt = gtpool.alloc().datum;
                gt.verts[0] = v0;
                gt.verts[1] = v1;
                gt.verts[2] = v2;
                gt.concrete = null;
                return gt;
            }

            public void releaseEdge(GenericEdgeType ge)
            {
                disconnectGE(ge);
                var ie = ge as IsctEdgeType;
                if (ie != null)
                {
                    iepool.free(ie);
                }
                else
                {
                    var oe = ge as OrigEdgeType;
                    Utils.ENSURE(oe != null);
                    oepool.free(oe);
                }
            }


            private Vec3 computeCoords(TopoEdge e, TopoTri t)
            {
                Empty3d.TriEdgeIn input = new Empty3d.TriEdgeIn();
                marshallArithmeticInput(input, e, t);
                //# ifdef USE_ORIGINAL_CODE
                //Vec3 coords = empty3d.coordsExact(input);
                //#else
                Vec3 coords = empty3d.coordsApprox(input);
                //#endif
                return coords;
            }

            private Vec3 computeCoords(TopoTri t0, TopoTri t1, TopoTri t2)
            {
                Empty3d.TriTriTriIn input = new Empty3d.TriTriTriIn();
                marshallArithmeticInput(input, t0, t1, t2);
                Vec3 coords = empty3d.coordsExact(input);
                return coords;
            }



            void marshallArithmeticInput(Empty3d.EdgeIn input, TopoEdge e)
            {
                input.p[0] = vPos(e.verts[0]);
                input.p[1] = vPos(e.verts[1]);
            }
            void marshallArithmeticInput(Empty3d.TriIn input, TopoTri t)
            {
                input.p[0] = vPos(t.verts[0]);
                input.p[1] = vPos(t.verts[1]);
                input.p[2] = vPos(t.verts[2]);
            }
            void marshallArithmeticInput(Empty3d.TriEdgeIn input, TopoEdge e, TopoTri t)
            {
                marshallArithmeticInput(input.edge, e);
                marshallArithmeticInput(input.tri, t);
            }
            void marshallArithmeticInput(Empty3d.TriTriTriIn input, TopoTri t0, TopoTri t1, TopoTri t2)
            {
                marshallArithmeticInput(input.tri[0], t0);
                marshallArithmeticInput(input.tri[1], t1);
                marshallArithmeticInput(input.tri[2], t2);
            }


            void quantizeVerts(Quantization quantizer)
            {
                if (base.mesh == null)
                    return;

                var N = base.mesh.verts.size();
                quantized_coords.resize(N, () => new Vec3());

                int write = 0;
                for (var v = base.verts.getFirst(); v != null; v = base.verts.getNext(v))
                {
                    //# ifdef _WIN32
                    Vec3 raw = base.mesh.verts[v.datum.@ref].pos;
                    //#else
                    //                    Vec3d raw = TopoCache::mesh.verts[v.ref].pos;
                    //#endif
                    quantized_coords[write].x = quantizer.quantize(raw.x);
                    quantized_coords[write].y = quantizer.quantize(raw.y);
                    quantized_coords[write].z = quantizer.quantize(raw.z);
                    v.datum.data = quantized_coords[write];
                    write++;
                }

                Utils.ENSURE(write == N);
            }

            public Vec3 vPos(TopoVert v)
            {
                return v.data as Vec3;
            }

            BBox3 buildBox(TopoEdge e)
            {
                Vec3 p0 = vPos(e.verts[0]);
                Vec3 p1 = vPos(e.verts[1]);
                return new BBox3(Vec3.min(p0, p1), Vec3.max(p0, p1));
            }
            BBox3 buildBox(TopoTri t)
            {
                Vec3 p0 = vPos(t.verts[0]);
                Vec3 p1 = vPos(t.verts[1]);
                Vec3 p2 = vPos(t.verts[2]);
                return new BBox3(Vec3.min(p0, Vec3.min(p1, p2)), Vec3.max(p0, Vec3.max(p1, p2)));
            }
        }
    }
}
